En este tutorial vamos a realizar paso por paso la extensión que llamamos
"Maybe", y que nos permite definir un tipo paramétrico Maybe<T> que tiene
dos constructores: Nothing<T> y Just J (donde J es un término de tipo T).

Para construir la extensión, tenemos que:
- crear el tipo
- crear las expresiones básicas Nothing y Just
- crear una función simple: isNothing
- crear una función más compleja: caseMaybe
- crear la extensión propiamente dicha y registrarla con el intérprete


1) Código "boilerplate"

Para crear la nueva extensión creamos un nuevo archivo de texto vacío
en la carpeta extensiones (idealmente con extensión .py) y pegamos el 
siguiente código en él:

#!/usr/bin/python
# -*- coding: utf8 -*-

from expresion import Expresion, Tipo, Exp, TipoExp, TypeException
from expresion import makeSintaxis

from booleans import Boolean
from lenguaje import Extension


Como verán, se trata de una serie de imports de objetos que vamos a necesitar
referenciar en nuestro código. Expresion y Tipo son las clases de las que vamos
a heredar para construir los términos y tipos de nuestra extensión (que se
construye a partir de la clase Extension, que importamos al final de todo).

Exp y TipoExp son los patrones de sintaxis de PyParsing que podemos usar
al definir sintaxis para referirnos a "una expresión cualquiera" o "un
término de tipo cualquiera". TypeException es la excepción que debemos producir
cuando haya un error de tipos

Finalmente, Boolean es la clase que
corresponde al tipo homónimo (y por tanto vive en la extensión correspondiente).
Es necesaria porque más adelante vamos a necesitar indicarle al sistema de tipado
que un término es de tipo Boolean (¿adivinan cual?), y para esto es necesario 
instanciar dicha clase.


2) Creando un nuevo tipo

En este caso no se puede utilizar el helper simpleTypeFactory porque este no es
un tipo "simple": se trata de un tipo paramétrico, y por lo tanto hay que definirlo
a mano extendiendo directamente la clase Tipo. Comencemos entonces por definir la
sintaxis:


#######################################
# Declaración del nuevo tipo Maybe(T) #
#######################################

class TipoMaybe(Tipo):
    @classmethod
    def sintaxis(cls):
        return makeSintaxis('Maybe(', TipoExp, ')')


Esta declaración decorada (la línea que comienza con @ se llama "decorator" en Python)
crea un método estático de la clase TipoMaybe (que luego se llama como TipoMaybe.sintaxis()).
En este caso utilizamos el helper makeSintaxis para decirle al intérprete que un término
que describe al tipo TipoMaybe tiene la sintaxis Maybe(TipoExp), donde TipoExp representa
a una expresión de tipo cualquiera (por ejemplo, Nat, Bool o incluso Maybe(Nat)!).

La definición sin makeSintaxis hubiera sido más larga y difícil de leer
(y además hubiera sido necesario importar Literal desde pyparsing!):

return Literal('Maybe(').suppress() + TipoExp + Literal(')').suppress()

Veamos ahora como se construye una instancia de TipoMaybe:

    def __init__(self, toks):
        self.tipo = toks[0]

La construcción es simple, únicamente se almacena como un atributo de instancia
el primer elemento de la lista toks, que corresponde al primer y único token que
matchea la sintaxis del tipo (recordemos que como utilizamos suppress() implícitamente
sobre los chunks 'Maybe(' y ')', estos no serán recibidos por el constructor). Sigamos:

    def __eq__(self, otro):
        return self.__class__ == otro.__class__ and \
               self.tipo == otro.tipo


Un TipoMaybe<T> será igual a otro si el segundo es un TipoMaybe (esa es la implementación
heredada de la clase Tipo, y no sería necesario sobrecargarla si fuera ésta la definición),
pero también si el tipo "englobado" por el Maybe es igual al otro. Recordemos que si bien
se utiliza el operador de igualdad, la noción asociada al mismo es la de unificación.

    def __str__(self):
        return 'Maybe(%s)' % self.tipo

Finalmente, el último método define la forma en que se convierte el objeto a una
representación en forma de string amigable para el usuario. En este caso (y en todos
los demás), nos limitamos a reproducir la sintaxis.

Con esto ya tenemos el nuevo tipo definido, y podemos dedicarnos a construir los
términos asociados al mismo.

2) Definición de expresiones básicas

A continuación vamos a definir las dos expresiones básicas del tipo Maybe(T),
empezando por Nothing (y esta vez heredando de Expresion en lugar de Tipo).

######################################
# Declaración de nuevas expresiones  #
######################################
    
class Nothing(Expresion):
    @classmethod
    def sintaxis(cls):
        return makeSintaxis('nothing(', TipoExp, ')')

La definición de sintaxis es análoga a la definición de sintaxis en el término
de tipo. Hay dos particularidades para notar en esta definición. La primera es
que la expresión que definimos como "nothing(T)" consta de una variable de tipo
(denotada por TipoExp) que permite tipar la expresión. En segundo lugar, no
hay que olvidar que los términos no deben llevar mayúsculas (ya que el parser
asume que las cosas que comienzan por mayúsculas dentro de una expresión son
variables). Por esta razón, el átomo creado se llama "nothing(T)" y no "Nothing(T)".

    def __init__(self, toks):
        self.tipo = toks[0]

    def __str__(self):
        return 'nothing(%s)' % self.tipo

Tanto el constructor como la función de conversión a string son exactamente
iguales a las de la definición del tipo y por tanto no requieren explicación adicional.
Veamos ahora qué ocurre con las funciones propias de la clase Expresion.

    def reducir(self):
        return self

La función reducir() es responsable de producir un término reducido (con semántica
big-step) a partir de la expresión actual. Sin embargo, en el caso de Nothing y por
tratarse de un valor, no hay que hacer ninguna reducción y es suficiente con devolver
una referencia al propio objeto que recibe el mensaje.

    def tipar(self, namespace):
        return TipoMaybe([self.tipo])

La función tipar() se encarga de producir una instancia del tipo correspondiente
a esta expresión. Para esto, nos servimos de la clase que definimos anteriormente
que instanciamos parametrizada en el tipo que parseamos a partir de la sintaxis.
Así, convertimos 'nothing(Nat)' en una instancia de TypeMaybe<Nat>.

Nótese la peculiaridad de que TipoMaybe recibe una lista de tokens, y por lo tanto
se debe pasar como parámetro [self.tipo] (entre corchetes).

    def sustituir(self, var, expresion):
        return self

Finalmente, el mecanismo de sustitución, por tratarse de un átomo inmutable,
se limita a devolver una referencia al propio objeto sin sustituir nada (ya que
no pueden aparecer variables dentro de esta expresión).


Veamos ahora la definición de Just J:

class Just(Expresion):
    @classmethod
    def sintaxis(cls):
        return makeSintaxis('just(', Exp, ')')

En este caso la diferencia respecto de la definición de nothing reside en
que la subexpresión es un término convencional y no una declaración de tipo.
Esto es posible puesto que a partir de dicho término se podrá inferir su tipo
y así establecer el tipado de esta expresión. Esto se refleja en la utilización
de Exp en lugar de TipoExp dentro de la definición de sintaxis.

    def __init__(self, toks):
        self.exp = toks[0]

    def __str__(self):
        return 'just(%s)' % self.exp

    def reducir(self):
        e = self.exp.reducir()
        return Just([e])

La definición de reducción se ajusta a lo definido por el Cálculo Lambda:
si M -> M' luego Just(M) -> Just(M'). Esto es precisamente lo que se
establece aquí, con una llamada recursiva a reducir() de la expresión
hija.

    def tipar(self, namespace):
        return TipoMaybe([self.exp.tipar(namespace)])

    def sustituir(self, var, expresion):
        return Just([self.exp.sustituir(var, expresion)])

Estos dos últimos casos son análogos al anterior: la implementación no hace más que
llamar recursivamente a las funciones apropiadas en la subexpresión y
construir a partir de dichos resultados los datos que le fueron pedidos.

Con esta última clase disponemos ya de los términos básicos que constituyen al
tipo paramétrico Maybe<T>. Sin embargo, para su uso posterior será conveniente
declarar algunos términos adicionales que faciliten su utilización.

3) Definición de un término derivado simple

A continuación nos concierne la declaración de la expresión isNothing(E)
que reduce a true si E es Nothing, o a false si E es Just J. Veamos su
implementación:

class IsNothing(Expresion):
    @classmethod
    def sintaxis(cls):
        return makeSintaxis('isNothing(', Exp, ')')

    def __init__(self, toks):
        self.exp = toks[0]

    def __str__(self):
        return 'isNothing(%s)' % self.exp

    def reducir(self):
        e = self.exp.reducir()
        return IsNothing([e])

    def sustituir(self, var, expresion):
        return IsNothing([self.exp.sustituir(var, expresion)])

Hasta este punto las definiciones son análogas a las vistas anteriormente.
Sin embargo, la implementación del tipado es más novedosa:

    def tipar(self, namespace):
        st = self.exp.tipar(namespace)
        if isinstance(st, TipoMaybe):
            return Boolean([])
        else:
            raise TypeException('Tipo del Término: %s \n' + 
                                'El tipo del término debe ser Maybe(T).' % st)

Observando la lógica del código, vemos que lo que hace es tipar el subtérmino
(es decir, si estamos lidiando con isNothing(E), obtiene el tipo de E) y a continuación
se fija si dicho tipo es realmente Maybe, verificando si es una instancia de TipoMaybe.
En caso afirmativo, el tipo de la expresión isNothing será Boolean, clase de la que se
devuelve una instancia. De otro modo, se envía una TypeException indicando de forma
informativa el error que se produjo, cual era el tipo esperado y cual el que se recibió.

4) Definición de un término derivado complejo

Como última declaración analizaremos la implementación de CaseMaybe, el observador
en base a constructores de las instancias de Maybe<T>.

class CaseMaybe(Expresion):
    @classmethod
    def sintaxis(cls):
        return makeSintaxis('caseMaybe(', TipoExp, ')', Exp, '; of nothing -> ', Exp, '; just(J) -> ', Exp)

    def __init__(self, toks):
        self.tipo, self.exp, self.resNothing, self.resJust = toks

    def __str__(self):
        return 'caseMaybe(%s) %s; of nothing -> %s; just(J) -> %s' % \
                (self.tipo, self.exp, self.resNothing, self.resJust)

Hasta este punto no se observan diferencias significativas. Es de notar
que para simplificar el ejemplo se utilizó el nombre fijo "J" para la variable
del case.

    def reducir(self):
        expR = self.exp.reducir()
        if isinstance(expR, Nothing):
            return self.resNothing.reducir()
        else:
            return self.resJust.sustituir('J', expR.exp).reducir()

La primera diferencia que se observa entre esta extensión y la anterior se da en el 
caso de la reducción: en este caso, es necesario para reducir exitosamente ligar
la variable J a la expresión asociada. Esto es precisamente lo que hace el código
si detecta que la expresión interna (self.exp) es una instancia de Just.

    def tipar(self, namespace):
        maybet = self.exp.tipar(namespace)
        trn = self.resNothing.tipar(namespace)
        
        ns_nuevo = namespace.copy()
        ns_nuevo['J'] = self.tipo
        trj = self.resJust.tipar(ns_nuevo)

        if isinstance(maybet, TipoMaybe) and trn == trj:
            return trn
        else:
            raise TypeException(('Tipo del Término: %s \n' +
                                'Tipo del bloque Case Nothing: %s \n' + 
                                'Tipo del bloque Case Just: %s \n' +
                                'El tipo de ambos casos debe ser compatible, y el tipo del término debía ser Maybe(T).') % 
                                (maybet, trn, trj))

La implementación de la regla de tipado es similar a la que vimos en isNothing, aunque el
chequeo a realizar es más complejo (ya que deben asegurarse más condiciones). En este caso,
se verifica que ambas 'ramas' del case tengan el mismo tipo después de ligar la variable J
en el caso de Just, así como que self.exp tenga el tipo apropiado según la declaración del case.

Una peculiaridad es el uso del namespace: nótese que a diferencia de los casos anteriores,
el contenido del mismo se modifica. El namespace es un diccionario nativo de Python, que mapea
strings a instancias de subclases de Tipo. Dado que los diccionarios (al igual que prácticamente
todo en Python) se pasan por referencia, es necesario copiar el namespace explícitamente antes 
de realizar la modificación del mismo ya que de otro modo se corre el riesgo de contaminar el
namespace de otras expresiones que compartan la misma instancia del diccionario.

    def sustituir(self, var, expresion):
        sMaybe = self.exp.sustituir(var, expresion)
        sresNothing = self.resNothing.sustituir(var, expresion)
        
        if var != 'J':
            sresJust = self.resJust.sustituir(var, expresion)
        else:
            sresJust = self.resJust

        return CaseMaybe([self.tipo, sMaybe, sresNothing, sresJust])

Por último, el mecanismo de sustitución también es más complejo:
en este caso, y como hay una variable ligada por esta expresión,
debe asegurarse de que no se realice una sustitución de la misma
por pedido de una expresión de nivel más alto. 

En este punto se establece el scope de la variable J, y se determina
que su valor dentro del bloque correspondiente del case será establecido
por self.reducir() y no por una sustitución anterior. Así, frente a un
pedido de sustitución, se reemplazará cualquier variable menos J, que es local
puesto que se define a nivel del Case.


5) Creación de la extensión

Finalmente, el único punto pendiente es la creación de la extensión propiamente dicha.
El código es autoexplicativo: no hay más que instanciar la clase Extension con una etiqueta
apropiada. 

######################################
# Armado de la nueva extensión       #
######################################

extensionMaybe = Extension('Maybe', expresiones=[Just, Nothing, IsNothing, CaseMaybe], tipos=[TipoMaybe])

# FIXME: ver como termina esto despues y actualizar
Para su posterior integración al lenguaje, la Extension deberá listarse al instanciar
la clase Lenguaje (que recibe una colección de extensiones a utilizar).
